package graph

import (
	"errors"
	"fmt"
	"gopkg.in/eapache/queue.v1"
)

// AdjacencyMatrixGraph 邻接矩阵实现的图存储结构
type AdjacencyMatrixGraph struct {
	data [][]int // 内部持有的二维数组
}

// AdjacencyListGraph 邻接表实现的图存储结构
type AdjacencyListGraph struct {
	found bool // 标记是否已经找到终点
	count int
	data  [][]int // 内部持有一组动态切片
}

// new 创建一个包含count个顶点的图
func new(count int) (graph *AdjacencyListGraph, err error) {
	if count < 1 {
		return nil, errors.New("count is illegal")
	}

	return &AdjacencyListGraph{
		count: count,
		data:  make([][]int, count),
	}, nil
}

// addEdge 添加一条边
func (receiver *AdjacencyListGraph) addEdge(vertex1, vertex2 int) {
	receiver.data[vertex1] = append(receiver.data[vertex1], vertex2)
	receiver.data[vertex2] = append(receiver.data[vertex2], vertex1)
}

// depthFirstSearch 深度优先搜索，搜到尽头就回退
func (receiver *AdjacencyListGraph) depthFirstSearch(start, end int) {
	// 记录已经访问过的节点
	visited := make([]bool, receiver.count)
	// 记录访问路径
	prev := make([]int, receiver.count)
	for i := 0; i < receiver.count; i++ {
		prev[i] = -1
	}
	receiver.returnDepthFirstSearch(start, end, visited, prev)
	printPath(prev, start, end)
}

// returnDepthFirstSearch 返回上个节点进行查找
func (receiver *AdjacencyListGraph) returnDepthFirstSearch(start, end int, visited []bool, prev []int) {
	// 当节点找到后，还会进入上层节点的循环搜索中，使用found可以逐一退出上层循环的搜索
	if receiver.found {
		return
	}
	visited[start] = true
	if start == end {
		receiver.found = true
		return
	}
	// 遍历当前节点的邻接节点
	for i := 0; i < len(receiver.data[start]); i++ {
		element := receiver.data[start][i]
		if !visited[element] {
			// 当前节点没访问过，继续深入下一级节点，若访问过则深入同级节点
			prev[element] = start
			receiver.returnDepthFirstSearch(start, end, visited, prev)
		}
	}
}

// breadthFirstSearch 广度优先搜索，把每一个点的连接点都遍历
func (receiver *AdjacencyListGraph) breadthFirstSearch(start, end int) {
	// 起点和终点相同，则无需继续查找
	if start == end {
		return
	}
	// 定义一个布尔类型数组保存已经访问过的节点
	visited := make([]bool, receiver.count)
	visited[start] = true
	// 定义一个队列保存待访问的节点
	forVisit := queue.New()
	forVisit.Add(start)
	// 保存每个访问过节点的前一个节点，用来记录访问路径
	prev := make([]int, receiver.count)
	for i := 0; i < receiver.count; i++ {
		prev[i] = -1
	}
	// 遍历各个需要遍历的节点
	for forVisit.Length() != 0 {
		// 取出队列中待遍历的节点
		element := forVisit.Remove().(int)
		// 遍历该节点的所有临接节点
		for i := 0; i < len(receiver.data[element]); i++ {
			// 取出临接节点
			en := receiver.data[element][i]
			// 该节点尚未访问过，记录该节点的上一个节点是element
			if !visited[en] {
				prev[en] = element
				if en == end {
					// 当前节点已经是要找的节点，则打印
					printPath(prev, start, end)
				}
			}
			// 标志en节点已经被访问过
			visited[en] = true
			forVisit.Add(en)
		}
	}
}

// printPath 用循环，可不用递归，每次更新前一个节点，然后倒序打印，只是需要额外存储空间
func printPath(prev []int, start, end int) {
	// 递归打印从start 到 end的路径
	if prev[end] != -1 && start != end {
		// 递归逐渐从最后一个节点找到start节点开始退出打印，由此打印出从start到end的路径
		printPath(prev, start, prev[end])
	}

	fmt.Println(start, "  ")
}
